package com.sicheng.蓝桥.练习题;

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class 乘积最大 {

    /**
     *
     */
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int count = 0, sign = 1;
        //count表示0的个数，当sign为-1时，表示当k为奇数并且数组最后一个元素小于0。
        long[] nums = new long[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextLong();
            if (nums[i] == 0) {
                count++;
            }
        }
        if (n - count < k) {
            //如果0的个数大于一个界限，则输出0
            System.out.println(0);
            return;
        }
        long res = 1;//存储最后的结果
        Arrays.sort(nums);
        if (k % 2 == 1) {//k为奇数
            res = nums[n - 1];
            n--;
            k--;
        }
        if (res < 0) {
            sign = -1;
        }
        int left = 0, right = n - 1;
        while (k > 0) {
            //t1表示数组前2个元素之积，t2表示数组后两个元素之积
            long t1 = nums[left] * nums[left + 1], t2 = nums[right] * nums[right - 1];
            /*
             这是最初始的状态，可以看出当 (t1 > t2 && sing == 1)或(t1 < t2 && sign == -1)的时候是res =
             (t1 % 1000000009 * res)%1000000009;当(t1 > t2 && sign == -1) 或(t1 <t2 && sign == 1)的时候
             res = (t2 % 1000000009 * res) %1000000009;

            if(t1 > t2){
                if(sign == 1){
                    res = (t1 % 1000000009 * res)%1000000009;
                }else {
                    res = (t2 % 1000000009 * res) %1000000009;
                }
            }else {
                if(sign == 1){
                    res = (t2 % 1000000009 * res)%1000000009;
                }else {
                    res = (t1 % 1000000009 * res) %1000000009;
                }
            }
            */
            //经过总结得出以下代码
            if (t1 * sign > t2 * sign) {
                res = (t1 % 1000000009 * res) % 1000000009;
                left += 2;
            } else {
                res = (t2 % 1000000009 * res) % 1000000009;
                right -= 2;
            }
            k -= 2;
        }
        System.out.println(res);

    }
}

